package com.example.origin.demo.suanfa.leecode;

/**
 * 输入：[2,7,9,3,1]
 * 输出：12
 * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
 *      偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 *
 * 定义子问题
 *      1.原问题要能由子问题表示。
 *        f(k)表示从k个房间偷取的最大金额，共n个房间，所以共n个子问题
 *      2.一个子问题的解要能通过其他子问题的解求出。
 *        f(k)可以通过 f(k−1) 和 f(k−2) 求出
 * 写出子问题的递推关系
 *      假设n个房子，每个房子存放H1，H2...Hn的金额，f(k)表示从k个房间偷取的最大金额。k个房子共两种偷法
 *      f(k-1) 和 f(k-2)+H1， k=1,f(1)=k1; k=2,f(2)=max(k1,k2);
 * 确定 DP 数组的计算顺序
 *      每个f(k)依赖f(k-1)和(k-2)。
 *
 */
public class No198Rob {


//    public static int rob(int[] nums) {
//        if (nums == null || nums.length == 0) {
//            return 0;
//        }
//        if (nums.length == 1) {
//            return nums[0];
//        }
//
//        // 动态规划数组，dp[i]表示考虑偷窃前i个房屋时，能够获得的最大金币数
//        int[] dp = new int[nums.length];
//        dp[0] = nums[0]; // 偷窃第一个房子
//        dp[1] = Math.max(nums[0], nums[1]); // 偷窃第二个房子，此时有两种选择：偷窃或不偷窃第一个房子
//
//        // 遍历剩余的房子
//        for (int i = 2; i < nums.length; i++) {
//            // dp[i]的选择基于偷窃或不偷窃当前房屋
//            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
//        }
//
//        return dp[nums.length - 1];
//    }

    public static int rob(int[] nums) {
        if (nums==null||nums.length==0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0],nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.length-1];
    }

    public static int rob2(int[] nums) {
        if (nums==null||nums.length==0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0],nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.length-1];
    }


    public static void main(String[] args) {
        int[] arr = {2, 7, 9, 3, 1};
        System.out.println(rob(arr));
        System.out.println(rob2(arr));
    }

}
